import java.util.*;

public class Leetcode1233 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString("/a".split("/")));
        System.out.println(removeSubfolders2(new String[]{"/a", "/a/b", "/c/d", "/c/d/e", "/c/f"}));
        System.out.println(removeSubfolders2(new String[]{"/a", "/a/b/c", "/a/b/d"}));
        System.out.println(removeSubfolders2(new String[]{"/a/b/c", "/a/b/ca", "/a/b/d"}));
        System.out.println(removeSubfolders2(new String[]{"/ah/al/am", "/ah/al"}));
    }


    public static List removeSubfolders1(String[] folder) {
        Arrays.sort(folder);

        Set<String> set = new TreeSet<>((a1, a2) -> a1.startsWith(a2 + "/") ? 0 : a1.compareTo(a2));
        Collections.addAll(set, folder);

        return new ArrayList<>(set);
    }

    public static List<String> removeSubfolders2(String[] folder) {
        Set<String> set = new HashSet<>(folder.length);
        Collections.addAll(set, folder);

        List<String> needRemove = new ArrayList<>();

        for (String s : folder) {
            boolean flag = true;

            char[] chars = s.toCharArray();
            for (int i = 1; i < chars.length; i++) {
                if (chars[i] == '/' && set.contains(s.substring(0, i))) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                needRemove.add(s);
            }
        }

        return needRemove;
    }

    public static List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);

        List<String> res = new ArrayList<>();
        for (int i = 0; i < folder.length; i++) {
            res.add(folder[i]);
            int j = i + 1;
            while (isSub(folder, i, j)) {
                j++;
            }

            i = j - 1;
        }

        return res;
    }

    private static boolean isSub(String[] folder, int i, int j) {
        if (j >= folder.length) {
            return false;
        }

        int startIndex = folder[j].indexOf(folder[i]);
        return startIndex == 0 && folder[j].charAt(startIndex + folder[i].length()) == '/';
    }
}
